#include<iostream>
using namespace std;
template <class T>
struct Node
{
    T data;
    struct Node<T>* next;
};

template <class T>
class LinkList
{
private:
    Node<T>* front;
public:
    LinkList()
    {
        front=new Node<T>;
        front->next=NULL;
    }
    LinkList(T a[],int n);
    ~LinkList();
    void PrintList();
    int GetLength();
    Node<T>* Get(int i);
    int Locate(T x);
    void Insert(int i,T x);
    T Delete(int i);
};
template<class T>
LinkList<T>::LinkList(T a[],int n)
{
    front=new Node<T>;
    Node<T>* r=front;
    for (int i = 0; i < n; i++)
    {
        Node<T>* s=new Node<T>;
        s->data=a[i];
        r->next=s;
        r=s;
    }
    r->next=NULL;
}
template<class T>
LinkList<T>::~LinkList()
{
    Node<T>* p=front;
    while (p)
    {
        front=p;
        p=p->next;
        delete front;
    } 
}
template<class T>
Node<T>* LinkList<T>::Get(int i)
{
    Node<T>* p=front->next;
    int j=1;
    while (p&&j!=i)
    {
        p=p->next;
        j++;
    }
    return p;
}
template<class T>
int LinkList<T>::Locate(T x)
{
    Node<T>* p=front->next;
    int j=1;
    while (p)
    {
        if (p->data==x)
        {
            return j;
        }
        p=p->next;
        j++;    
    }
    return -1;
}
template<class T>
void LinkList<T>::Insert(int i,T x)
{
    Node<T>* p=front;
    if (i!=1)
    {
        p=Get(i-1);
    }
    if (p)
    {
        Node<T>* s=new Node<T>;
        s->data=x;
        s->next=p->next;
        p->next=s;
    }
    else throw"插入位置错误";
}
template<class T>
T LinkList<T>::Delete(int i)
{
    Node<T>* p=front;
    if (i!=1)
    {
        p=Get(i-1);
    }
    Node<T> *q=p->next;
    p->next=q->next;
    T x=q->data;
    delete q;
    return x;
}
template<class T>
int LinkList<T>::GetLength()
{
    Node<T>* p=front;
    int i=0;
    while (p!=NULL)
    {
        p=p->next;
        i++;
    }
    return i;
}
template <class T>
void LinkList<T>::PrintList()
{
    Node<T>* p=front->next;
    while (p!=NULL)
    {
        p->data.print();
        p=p->next;
    }
    cout<<endl;
}